The KDM4/JMJD2 Jumonji C-containing histone lysine demethylases (KDM4A-KDM4D), which selectively remove the methyl group(s) from tri/dimethylated lysine 9/36 of H3, modulate transcriptional activation and genome stability. The overexpression of KDM4A/KDM4B in prostate cancer and their association with androgen receptor suggest that KDM4A/KDM4B are potential progression factors for prostate cancer. Here, we report the crystal structure of the KDM4B·pyridine 2,4-dicarboxylic acid·H3K9me3 ternary complex, revealing the core active-site region and a selective K9/K36 site. A selective KDM4A/KDM4B inhibitor, 4, that occupies three subsites in the binding pocket is identified by virtual screening. Pharmacological and genetic inhibition of KDM4A/KDM4B significantly blocks the viability of cultured prostate cancer cells, which is accompanied by increased H3K9me3 staining and transcriptional silencing of growth-related genes. Significantly, a substantial portion of differentially expressed genes are AR-responsive, consistent with the roles of KDM4s as critical AR activators. Our results point to KDM4 as a useful therapeutic target and identify a new inhibitor scaffold.